package com.duoduo.栈和队列;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 字符串解码394
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * <p>
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * <p>
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * <p>
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 * <p>
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * https://leetcode.cn/problems/decode-string/solutions/19447/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
 * @author: chaidl  ！
 * @create: 2022-04-10 16:39
 */
public class 字符串解码394 {
	public static void main(String[] args) {
		System.out.println(decodeString("3[a2[c]]"));
	}
	public static String decodeString(String s) {
		StringBuilder res=new StringBuilder();
		int num=0;
		//定义两个栈
		LinkedList<Integer> numStack=new LinkedList<>();
		LinkedList<String> strStack=new LinkedList<>();
		for(Character c:s.toCharArray()){
			// 当 c 为数字时，将数字字符转化为数字 num，用于后续倍数计算；
			if(c>='0' && c<='9'){
				//如果是数字就暂存起来
				num=num*10+Integer.parseInt(c+"");
			}else if(c=='['){
				//当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 000：
				// 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
				// 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串。
				// 进入到新 [ 后，res 和 multi 重新记录。
				//如果是左括号，就将他们各自入栈
				numStack.addLast(num);
				strStack.addLast(res.toString());
				num=0;
				res=new StringBuilder();
			}else if(c==']'){
				//如果是右括号，出栈遍历
				StringBuilder tmpStr=new StringBuilder();
				int tmpNum=numStack.removeLast();
				for(int i=0;i<tmpNum;i++){
					tmpStr.append(res);
				}
				res=new StringBuilder(strStack.removeLast()+tmpStr);

			}else{
				//当 c 为字母时，在 res 尾部添加 c；
				res.append(c);
			}
		}
		return res.toString();
	}
	public static String decodeString1(String s) {
		String res = "";
		Stack<Integer> countStack = new Stack<>();
		Stack<String> resStack = new Stack<>();
		int idx = 0;
		while (idx < s.length()) {
			char cur = s.charAt(idx);
			/*处理数字*/
			if (Character.isDigit(cur)) {
				StringBuffer ret = new StringBuffer();
				while (Character.isDigit(s.charAt(idx))) {
					ret.append(s.charAt(idx++));
				}
				countStack.push(Integer.parseInt(ret.toString()));
			} else if (cur == '[') {
				/*处理“[”*/
				resStack.push(res);
				res = "";
				idx++;
			} else if (cur == ']') {
				/*处理“]”,处理相匹配的“[”之间的字符*/
				StringBuffer temp = new StringBuffer(resStack.pop());
				int repeatTimes = countStack.pop();
				for (int i = 0; i < repeatTimes; i++) {
					temp.append(res);
				}
				res = temp.toString();
				idx++;
			} else {
				/*处理普通字符*/
				res += s.charAt(idx++);
			}
		}
		return res;
	}
}
